#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int maximizeWin(vector<int>& prizePositions, int k) {
        const int N = 1e5 + 100;
        int dp[N] = { 0 };
        int ret = 0;
        for (int left = 0, right = 0; right < prizePositions.size(); right++)
        {
            while (prizePositions[right] - prizePositions[left] > k)
            {
                ++left;
            }
            ret = max(ret, right - left + 1 + dp[left]);
            dp[right + 1] = max(dp[right], right - left + 1);
        }

        return ret;
    }
};